This invention relates to a method of reversibly encoding a compressed data stream. In recent years, technologies to compress data have come to be widely used to accommodate the rapid increase in the amount of data processed by computers. In data compression technology, reversible encoding methods allow restoring data to the state before compression and non-reversible encoding methods do not allow restoration of data to its original state. The non-reversible encoding methods are primarily used in compressing image data. The reversible encoding methods are generally used in compressing data such as program data, text data and dictionary data.
An example of a reversible encoding method is the so-called LZ (Lempel-Ziv) method. This encoding method entails examining whether or not the data string to be compressed matches any data string that appeared previously in the data stream. If there is a data string that matches, this particular method codifies the data string with the length of the data string and the separation between the matching data strings (offset) in the data stream. "Data string" here means a series of data in prescribed units (for example, one byte). If there is no previous data string that matches with the data string to be compressed, the noncompressed (also called "solid") data string itself is appended to the encoded data string.
The format of a conventional LZ-type encoded data string is illustrated below.
&lt;Suffix&gt; &lt;Noncompressed byte data or LZ compressed data&gt;Repeat
Since there is a mix of noncompressed-type byte data and LZ-type compressed data (includes encoded data for matching length and the offset) in the entire encoded data stream, a prefix is attached to each encoded data unit as an identifier. A single unit of encoded data can be either a noncompressed data byte or an LZ compressed data unit.
FIG. 1 is a state transition diagram of data compression under the conventional LZ encoding method. In previous methods, the noncompressed-type byte data and the LZ-type compressed data were aligned in an arbitrary order. Because of this, a prefix was attached to each unit of encoded data at the time of compression in order to identify each type of encoded data unit when the data is expanded.
In the conventional LZ-type encoding method, a sufficient compression ratio is not necessarily achieved in the event a large percentage of the encoded data stream is noncompressed-type data because the conventional method requires the attachment of a prefix to each encoded data unit. The invention described herein offers a reversible encoding method for data that provides relatively high compression ratio even if the resulting encoded data stream has a large percentage of noncompressed-type data units.